package com.example.demo.offer;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private Map<Integer,DLinkedNode> cacheMap = new HashMap<>();
    private DLinkedNode head,tail;
    private int size;
    private int capacity;

    public static void main(String[] args) {

    }

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode dLinkedNode = cacheMap.get(key);
        if(dLinkedNode == null){
            return -1;
        }
        moveToHead(dLinkedNode);
        return dLinkedNode.value;
    }

    public void put(int key, int value) {
        DLinkedNode dLinkedNode = cacheMap.get(key);
        if(dLinkedNode == null){
            DLinkedNode newNode = new DLinkedNode(key,value);
            cacheMap.put(key,newNode);
            addToHead(newNode);
            size++;
            if(size > capacity){
                DLinkedNode tailNode = removeTailNode();
                cacheMap.remove(tailNode.key);
                size--;
            }
        }else{
            dLinkedNode.value = value;
            moveToHead(dLinkedNode);
        }
    }

    private DLinkedNode removeTailNode() {
        DLinkedNode prev = tail.prev;
        removeNode(prev);
        return prev;
    }

    private void moveToHead(DLinkedNode dLinkedNode) {
        removeNode(dLinkedNode);
        addToHead(dLinkedNode);
    }

    private void addToHead(DLinkedNode dLinkedNode) {
        dLinkedNode.next = head.next;
        dLinkedNode.prev = head;
        head.next.prev = dLinkedNode;
        head.next = dLinkedNode;
    }

    private void removeNode(DLinkedNode dLinkedNode) {
        dLinkedNode.prev.next = dLinkedNode.next;
        dLinkedNode.next.prev = dLinkedNode.prev;
    }


}

class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
    public DLinkedNode() {}
    public DLinkedNode(int key, int value) {this.key = key; this.value = value;}
}


